package mo.leetcode_top;

import java.util.*;

public class L347 {

    public int[] topKFrequent(int[] nums, int k) {

        Map<Integer, Integer> num2count = new HashMap<>();
        for (int num : nums) {
            Integer count = num2count.get(num);
            if (count == null) {
                num2count.put(num, 1);
            } else {
                count++;
                num2count.put(num, count);
            }
        }

        int maxTimes = 0;
        Map<Integer, List<Integer>> count2num = new HashMap<>();
        for (Map.Entry<Integer, Integer> entry : num2count.entrySet()) {
            if (entry.getValue() > maxTimes) {
                maxTimes = entry.getValue();
            }
            List<Integer> keys = count2num.get(entry.getValue());
            if (keys == null) {
                keys = new ArrayList<>();
            }
            keys.add(entry.getKey());
            count2num.put(entry.getValue(), keys);
        }

        int[] res = new int[k];
        int i =  0;
        while (i < k) {
            if (count2num.containsKey(maxTimes)) {
                List<Integer> keys = count2num.get(maxTimes);
                for (int j = 0; j < keys.size(); j++) {
                    res[i++] = keys.get(j);
                }
            }
            maxTimes--;

        }

        return res;
    }

    public static void main(String[] args) {
        L347 test = new L347();
        System.out.println(Arrays.toString(test.topKFrequent(new int[]{5, 3, 1, 1, 1, 3, 73, 1}, 2)));
    }

}
